// 189.轮转数组
package LeetcodeHot100;

public class Solution189 {
    public void rotate(int[] nums, int k) {
        int length = nums.length;
        if ((k = k % length) == 0) // 这里需要取余，否则数组下标可能越界
            return;
        int index = -1; // 初始下标
        int count = 0; // 记录轮转的次数

        while (count != length) {
            index++; // 环状替换的初始下标
            int temp = nums[index]; // 记录第一个被替换的元素
            int to = index; // 记录当前被替换的位置
            // 一次环状替换开始
            do {
                int from = (to + length - k) % length; // 记录当前使用哪个元素替换
                // 判断是否是第一个元素，如果是，则需要使用temp
                if (from != index) {
                    nums[to] = nums[from];
                    count++;
                    to = from;
                } else {
                    nums[to] = temp;
                    count++;
                    to = from;
                }
            } while (to != index);
        }
    }
}
